package C010;

import org.w3c.dom.Node;

/**
 * ClassName: OrderedLinkedListMerging
 * Package: C010
 * Description:
 *
 * @Author BCXJ
 * @Create 2024/11/29 14:23
 * @Version 1.0
 * @Since 1.0
 */
public class OrderedLinkedListMerging {

    static class ListNode {
        int val;
        ListNode next;

        public ListNode(int val) {
            this.val = val;
        }
    }

    public static void main(String[] args) {
        ListNode listNode1 = new ListNode(1);
        ListNode listNode2 = new ListNode(2);
        ListNode listNode3 = new ListNode(4);
        listNode1.next = listNode2;
        listNode2.next = listNode3;
        ListNode listNode4 = new ListNode(1);
        ListNode listNode5 = new ListNode(3);
        ListNode listNode6 = new ListNode(4);
        listNode4.next = listNode5;
        listNode5.next = listNode6;
        ListNode merge = merge(listNode1, listNode4);
        while (merge != null) {
            System.out.println(merge.val);
            merge = merge.next;
        }
    }

    public static ListNode merge(ListNode list1, ListNode list2) {
        if(list1 == null || list2 == null) {
            return list1 == null ? list2 : list1;
        }
        ListNode res = list1.val < list2.val ? list1 : list2;
        ListNode cur1 = res.next;
        ListNode cur2 = res == list1 ? list2 : list1;
        ListNode pre = res;
        while(cur1 != null && cur2 != null) {
            if(cur1.val <= cur2.val) {
                pre.next = cur1;
                cur1 = cur1.next;
            }else {
                pre.next = cur2;
                cur2 = cur2.next;
            }
            pre = pre.next;
        }
        pre.next = cur1 == null ? cur2 : cur1;
        return res;
    }

}
